package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         132,
		Discription: "将字符串分割成若干子串，使得每个子串都是回文的最小分割数",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func MinCut(s string) int {
	n := len(s)
	//dp[i][j]表示s[i:j]是否构成回文串
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n+1)
		dp[i][i] = true
		dp[i][i+1] = true
	}

	for i := n - 2; i >= 0; i-- {
		for j := i + 2; j <= n; j++ {
			dp[i][j] = s[i] == s[j-1] && dp[i+1][j-1]
		}
	}

	//minCount[j]表示s[0:j]的最小分割数
	minCount := make([]int, n+1)
	for i := 2; i <= n; i++ {
		minCount[i] = i - 1
	}
	for j := 1; j <= n; j++ {
		//容易错：假如本身就是回文，直接返回0
		if dp[0][j] {
			minCount[j] = 0
		}
		//从[j-1:j]遍历到[1:j]，找最小分割数
		for i := j - 1; i >= 1; i-- {
			if dp[i][j] {
				minCount[j] = min(minCount[j], 1+minCount[i])
			}
		}
	}

	return minCount[n]
}
